Church Numerals
Volume Number: 7
Issue Number: 6
Column Tag: Lisp Listener
Going Back to Church 
By André van Meulebrouck, Chatsworth, CA
“Scheme is a very clear language and its tutors follow a zen philosophy.
Anything unessential or controversial (i.e. not so well understood) is thrown away. The
latest Scheme report is an admirable document and as semantical analysis progresses,
slicing molecules then atoms and after that quarks I dare say that the revised∞ report
on Scheme will converge to l-calculus.” Christian Queinnec [Queinnec, 1990].
This article will attempt to prompt interesting insights into recursive
functions, and evaluation strategies via looking at an alternate numeric system
(Church numerals). It also touches on various concepts such as object oriented
programming, dynamic scoping, and lazy streams.
(Sneak preview: imagine a numeric system wherein the operations; addition,
subtraction, multiplication, and exponentiation all take roughly the same amount of
time to compute regardless of the size of the numeric arguments! Church numerals
accomplish this by returning functions that “promise” to do the computation later, yet
these “promises” are still bona fide Church numerals that can be used in further
computations. There are of course trade-offs from such “laziness”. For instance,
when Church numerals are converted to regular numbers, computations that weren’t
done previously must be completed. Tools are provided for the reader to explore these
trade-offs.)
A Hope for the Future?!?
Perhaps you might think of Alonzo Church’s l-calculus (and numerals) as
impractical mental gymnastics, but consider: many times in the past, seemingly
impractical theories became the underpinnings of future technologies (for instance:
Boolean Algebra).